package com.xinwei.leetcode.数组;

import org.ietf.jgss.GSSException;

import java.util.Arrays;

// https://leetcode-cn.com/problems/3sum-closest/
public class _16_最接近的三数之和 {
    public static int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        int result = 0; // 用于记录结果
        int minDistance = Integer.MAX_VALUE; // 用于记录差值的最小值
        for (int first = 0; first < len - 2; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < len; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                int third = len - 1;
                while (second < third) {
                    // 当前差值与最小差值进行比较
                    int sum = nums[first] + nums[second] + nums[third];
                    int cur = Math.abs(sum - target);
                    if (cur < minDistance) {
                        minDistance = cur;
                        result = sum;
                    }
                    if (nums[first] + nums[second] + nums[third] < target) {
                        // 三数之和小于目标值
                        second++;
                        while (second < third && nums[second] == nums[second - 1]) {
                            second++;
                        }
                    }else if (nums[first] + nums[second] + nums[third] == target){
                        return result = target;
                    }else {
                        // 三数之和大于目标值
                        third--;
                        while (second < third && nums[third] == nums[third + 1]) {
                            third--;
                        }
                    }

                }
            }
        }
        return result;
    }
}
